package summary;

import java.util.*;

/**
 * @Author: 海琳琦
 * @Date: 2022/4/19 15:01
 * https://leetcode-cn.com/problems/word-ladder-ii/
 */
public class Title126 {

    public static List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> result = new ArrayList<>();
        Set<String> allWords = new HashSet<>(wordList);
        if (!wordList.contains(endWord)) {
            return result;
        }
        // 第 1 步：广度优先遍历建图
        // 记录扩展出的单词是在第几次扩展的时候得到的，key：单词，value：在广度优先遍历的第几层
        // 单词，单词所在的层数
        Map<String, Integer> steps = new HashMap<>();
        steps.put(beginWord, 0);
        //判断该单词是由那些单词扩展而来
        Map<String, List<String>> paths = new HashMap<>();
        //是否发现再短路径
        boolean found = false;
        int step = 1;
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        while (!queue.isEmpty()) {
            //本层所有的数据个数
            int size = queue.size();
            for (int q = 0; q < size; q++) {
                //弹出上一次加入的所有单词
                String word = queue.poll();
                //替换每个单词的每个位置 bfs
                for (int i = 0; i < word.length(); i++) {
                    for (char j = 'a'; j <= 'z'; j++) {
                        //每次获得一个新的
                        char[] chars = word.toCharArray();
                        chars[i] = j;
                        //一个新的单词
                        String newWord = String.valueOf(chars);
                        //如果当前层包括该新单词，则建立图关系
                        if (steps.containsKey(newWord) && step == steps.get(newWord)) {
                            paths.get(newWord).add(word);
                        }
                        if (!allWords.contains(newWord)) {
                            continue;
                        }
                        // 如果从一个单词扩展出来的单词以前遍历过，距离一定更远，为了避免搜索到已经遍历到，
                        // 且距离更远的单词，需要将它从 dict 中删除
                        allWords.remove(newWord);
                        // 这一层扩展出的单词进入队列
                        queue.offer(newWord);
                        // 记录 nextWord 从 currWord 而来
                        paths.computeIfAbsent(newWord, k -> new ArrayList<>()).add(word);
                        // 记录 nextWord 的 step
                        steps.put(newWord, step);
                        if (newWord.equals(endWord)) {
                            found = true;
                        }
                    }
                }
            }
            step++;
            if (found) {
                break;
            }
        }
        // 第 2 步：深度优先遍历找到所有解，从 endWord 恢复到 beginWord ，所以每次尝试操作 path 列表的头部
        if (found) {
            LinkedList<String> path = new LinkedList<>();
            path.add(endWord);
            dfs(paths, path, beginWord, endWord, result);
        }
        return result;
    }

    public static void dfs(Map<String, List<String>> paths, LinkedList<String> path, String beginWord, String cur, List<List<String>> res) {
        if (cur.equals(beginWord)) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (String preWord : paths.get(cur)) {
            path.addFirst(preWord);
            dfs(paths, path, beginWord, preWord, res);
            path.removeFirst();
        }
    }

    public static List<List<String>> findLadders1(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> result = new ArrayList<>();
        Set<String> allWord = new HashSet<>(wordList);
        if (!allWord.contains(endWord)) {
            return result;
        }
        //记录每个节点的路径长度
        Map<String, Integer> steps = new HashMap<>();
        steps.put(beginWord, 0);
        //建立图关系  终点 -> 起点
        Map<String, List<String>> graph = new HashMap<>();
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        int step = 1;
        boolean found = false;
        while (!queue.isEmpty()) {
            int curSize = queue.size();
            //这一层bfs
            for (int i = 0; i < curSize; i++) {
                String word = queue.poll();
                //变换每一个单词
                for (int j = 0; j < word.length(); j++) {
                    for (char k = 'a'; k <= 'z'; k++) {
                        char[] chars = word.toCharArray();
                        chars[j] = k;
                        String nextWord = String.valueOf(chars);
                        //如果当前层包括同一个节点，创建图关系
                        if (steps.containsKey(nextWord) && step == steps.get(nextWord)) {
                            graph.get(nextWord).add(word);
                        }
                        if (!allWord.contains(nextWord)) {
                            continue;
                        }
                        allWord.remove(nextWord);
                        queue.offer(nextWord);
                        //第一次出现
                        graph.computeIfAbsent(nextWord, g -> new ArrayList<>()).add(word);
                        //记录当前层的step
                        steps.put(nextWord, step);
                        if (nextWord.equals(endWord)) {
                            found = true;
                        }
                    }
                }
            }
            step++;
            //找到后，bfs完本层后再跳出
            if (found) {
                break;
            }
        }
        if (found) {
            LinkedList<String> onePath = new LinkedList<>();
            onePath.add(endWord);
            dfs1(graph, beginWord, endWord, onePath, result);
        }
        return result;
    }

    private static void dfs1(Map<String,List<String>> graph, String beginWord, String cur, LinkedList<String> onePath, List<List<String>> result) {
        if (cur.equals(beginWord)) {
            result.add(new ArrayList<>(onePath));
            return;
        }
        for (String preWord : graph.get(cur)) {
            onePath.addFirst(preWord);
            dfs1(graph, beginWord, preWord, onePath, result);
            onePath.removeFirst();
        }
    }

    public static void main(String[] args) {
//        findLadders1("hit", "cog", Arrays.asList("hot", "dot", "dog", "lot", "log", "cog"));
        List<String> strings = Arrays.asList("a", "b", "c");
        findLadders1("a", "c", strings);
    }
}
